package 数据结构.链表.单链表;

import java.util.Stack;

//管理英雄
public class SingleLinkedList {
//1、初始化头节点，头节点不要动,不存放数据,作为全局变量
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode gerhead(){
        return head;
    }

//2、不考虑编号添加节点到单项链表
//    思路：但不考虑编号顺序时
//    1、找到当前链表的最后节点
//    2、将最后节点的next域指向 新的节点
    public void add (HeroNode heroNode){
//        因为head节点不能动，因此我们需要辅助遍历temp
        HeroNode temp = head;
//        遍历链表，找到最后
        while(temp.next != null){
            temp = temp.next;
        }
       /* while(true){
            if(temp.next == null)
                break;
            temp = temp.next;
        }*/
//        当while循环结束后，表示temp就指向了最后节点，就把最后的节点指向新的节点
        temp.next = heroNode;
    }
//    考虑编号添加到指定位置
    /*
    * 思路：1、首先找到添加节点的位置，通过辅助变量temp（指针），通过遍历实现
    * 2、将新的节点.next = temp.next
    * 3、将temp.next = 新的节点（2、3两点通过画图可自己理解）
    * */
    public void addByOrder(HeroNode heroNode){
//        因为头节点布恩那个东，仍然通过辅助指针帮助找到变量位置
//        因为单链表，我们找的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        Boolean flag = false;
        while (temp.next != null) {//如果temp.next等于空，说明当前temp已经在链表最后面
            if (temp.next.no > heroNode.no) {//如果temp.next.no大于he.no;说明位置已经找到，就在temp的后面插入
                break;
            }
            if (temp.next.no == heroNode.no) {//如果等于，说明该编号的节点已经存在，修改flag为true
                flag = true;
                break;
            }
            temp=temp.next;
        }
        if (flag) {
            System.out.println(heroNode.no + "该节点已存在");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }


    }

//    链表的修改
//    假设根据no编号来修改其他的信息，及no不能改
    public void update(HeroNode newHeroNode){
        if (head.next == null) {//第一步，先判断链表是否为空
            System.out.println("链表为空，无法修改");
            return;
        }
        HeroNode temp = head;//设辅助指针
        Boolean flag = false;// 定义 flag 判断是否找到，默认false未找到
        while (temp.next != null) {//当链表的next不为空时，就是还没到最后一个时
            if (temp.next.no == newHeroNode.no) {//如果找到no编号相等的
                flag = true;
                break;//记得要跳出。不然会空指针报错
            }
            temp = temp.next;//没有就继续往后移
        }
        if (flag) {//判断flag
            temp.next.nickname = newHeroNode.nickname;
            temp.next.name = newHeroNode.name;
        } else {
            System.out.println(newHeroNode.no+"此节点在链表中未找到");
        }
    }

/*从单链表中删除某一个节点
*   1、首先遍历找到该要删除节点的前一个结点temp
*   2、让这个temp.next=temp.next.next即可
*   3、被删除的这个节点将不会有其他引用指向，会被垃圾回收机制回收。
*   4、如果删除的是最后一个节点，就是前一个结点的next会赋值为null，不用管。
* */
    public void delete(int no){
        HeroNode temp = head;//辅助节点
        Boolean flag = false;//标识是否找到
        if (temp.next == null) {
            System.out.println("该链表为空，无法删除");
            return;
        }
        while (temp.next != null) {//当没有遍历到最后
            if (temp.next.no == no) {//找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("未找到"+no+"该节点，无法删除");
        }
    }

//链表的翻转
    /*
    * 思路：把指向后一个节点变为指向前一个节点
    *   利用三个辅助指针完成,分别指向前一个节点，当前节点，下一个节点，将当前节点的next指向前一个结点，然后三个指针往后移，直到最后一个节点
    * */
    public void fanzhuan() {
        HeroNode temp = head;
        HeroNode pretemp = null;
        HeroNode nextemp = null;
        if (temp.next == null) {
            System.out.println("链表为空");
            return;
        }
        while (temp != null) {
            nextemp = temp.next;
            temp.next = pretemp;
            pretemp = temp;
            temp = nextemp;
        }
        while (pretemp.next != null) {
            System.out.println(pretemp);
            pretemp = pretemp.next;
        }

    }
/*
*   思路，头插法翻转，遍历链表，然后将每一个节点都以头插法的放心加入新的空链表。
* */
    public void fanzhuan2() {//测试正确
        if (head == null || head.next == null) {
            return ;
        }
        HeroNode newnode = new HeroNode(0,"","");
        HeroNode cur = head.next;
        HeroNode next = head.next;
        while (cur != null) {
            next = cur.next;
            cur.next = newnode.next;
            newnode.next = cur;
            cur = next;
        }
        head.next = newnode.next;
    }
//    链表的从尾到头打印
    /*
    * 思路  解法一：先将链表翻转，在进行打印（不推荐，破坏了原有链表的结构）
    *
    *       解法二：利用栈的先进后出原理（像井）先把链表所有数加入栈中，然后从栈中一个个拿出来打印
    * */
    public void reversePrint(HeroNode head){
        if (head.next == null) {
            return ;
        }
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }


    }

//  合并两个有序链表（未完成）


//    显示链表【遍历】
    public void list(){
//        先判断是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
//        因为头节点不能为空，所以需要辅助变量来帮助遍历
        HeroNode temp = head.next;
        while(temp != null){
//            输出节点信息：打印的时候自动调用tostring（）方法
            System.out.println(temp);
//            记得要接着指向下一个节点,一定要后移
            temp = temp.next;
        }
    }
}
